package simple;

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/2/12 19:38
 */
public class No459_重复的子字符串 {
    public static void main(String[] args) {
        Solution459 solution459 = new Solution459();
        String pattern = "ABAABCDABAAB";
        //String pattern = "ABAABACDABAABABA";
        int[] next = solution459.getNext(pattern);
        System.out.println();
        boolean flag = solution459.repeatedSubstringPattern("aexaexaex");
        System.out.println(flag);
    }
}

class Solution459 {
    public boolean repeatedSubstringPattern(String s) {
        // 写在前面:
        // KMP算法:理解难度系数0.1
        // 不正经算法系列将KMP难度系数降低到0.9
        // 祝大家秒懂挖~
        // 有关KMP算法详细No28_3_(1-4) 有全套视频
        // 由于该视频是前期视频有大量杂音,务必将音量调低食用~~
        // 而且没有字幕,有小伙伴看的吃力
        // 现在将KMP算法重新讲解,加上字幕
        // 希望能帮助到大家
        //排除索引(0,n)
        int kmp = kmp(s + s, s);
        return kmp != -1;
    }

    //t:s+s
    //pattern:匹配字符串s
    public int kmp(String t, String pattern) {
        //t:指针
        int red = 1;
        //pattern指针
        int green = 0;
        //next数组
        int[] next = getNext(pattern);
        while (red < t.length() - 1 && green < pattern.length()) {
            if (green == -1 || t.charAt(red) == pattern.charAt(green)) {
                red++;
                green++;
            } else {
                //跳跃
                green = next[green];
            }
        }
        //red或green出
        //green出
        if (green >= pattern.length()) {
            return red - pattern.length();
        }
        //red出
        return -1;
    }

    //获取next数组
    public int[] getNext(String pattern) {
        int red = -1;
        int green = 0;
        int[] next = new int[pattern.length() + 1];
        next[0] = -1;
        //构造next数组
        while (green <= pattern.length() - 1) {
            if (red == -1 || pattern.charAt(red) == pattern.charAt(green)) {
                red++;
                green++;
                next[green] = red;
            } else {
                red = next[red];//注意理解
            }
        }
        return next;
    }
}



    //public boolean repeatedSubstringPattern(String s) {
    //    // Double kill!!!
    //    // s+s
    //    // check
    //
    //    // ??
    //    String data = s + s;
    //    String check = data.substring(1, data.length() - 1);
    //    return check.contains(s);
    //}

    //public boolean repeatedSubstringPattern(String s) {
    //    //abcabc...(10000个abc)abaabc
    //    // 拼接
    //    for (int i = 1; i <= s.length() / 2;i++) {
    //        //前缀切,拼接后面
    //        String check = s.substring(i) + s.substring(0, i);
    //        //让切分的(拼好)跟s相同
    //        if (check.equals(s)) {
    //            return true;
    //        }
    //    }
    //    return false;
    //}



    //public boolean repeatedSubstringPattern(String s) {
    //    // 暴力法
    //    //轮次
    //    int count = s.length() / 2 + 1;
    //    out:for (int i = 1; i <= count; i++) {
    //        //i:轮次
    //        //获取base
    //        String base = s.substring(0, i);
    //        //获取检查的元素
    //        for (int j = i; j + i <= s.length(); j += i) {
    //            String check = s.substring(j, j + i);
    //            //如果chcek!=base跳过轮次
    //            if (!check.equals(base)) {
    //                continue out;
    //            }
    //            //如果没有跳过,说明复读顺利!!
    //            if (i + j == s.length()) {
    //                return true;
    //            }
    //        }
    //    }
    //    return false;
    //}






